home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / SYM.C < prev    next >
C/C++ Source or Header  |  1992-12-08  |  9KB  |  363 lines
  1. /*
  2.  * Simple symbol table manager using coalesced chaining to resolve collisions
  3.  *
  4.  * Doubly-linked lists are used for fast removal of entries.
  5.  *
  6.  * 'sym.h' must have a definition for typedef "Sym".  Sym must include at
  7.  * minimum the following fields:
  8.  *
  9.  *        ...
  10.  *        char *symbol;
  11.  *        struct ... *next, *prev, **head, *scope;
  12.  *        unsigned int hash;
  13.  *        ...
  14.  *
  15.  * 'template.h' can be used as a template to create a 'sym.h'.
  16.  *
  17.  * 'head' is &(table[hash(itself)]).
  18.  * The hash table is not resizable at run-time.
  19.  * The scope field is used to link all symbols of a current scope together.
  20.  * Scope() sets the current scope (linked list) to add symbols to.
  21.  * Any number of scopes can be handled.  The user passes the address of
  22.  * a pointer to a symbol table
  23.  * entry (INITIALIZED TO NULL first time).
  24.  *
  25.  * Available Functions:
  26.  *
  27.  *    zzs_init(s1,s2)    --    Create hash table with size s1, string table size s2.
  28.  *    zzs_done()        --    Free hash and string table created with zzs_init().
  29.  *    zzs_add(key,rec)--    Add 'rec' with key 'key' to the symbol table.
  30.  *    zzs_newadd(key)    --    create entry; add using 'key' to the symbol table.
  31.  *    zzs_get(key)    --    Return pointer to last record entered under 'key'
  32.  *                        Else return NULL
  33.  *    zzs_del(p)        --    Unlink the entry associated with p.  This does
  34.  *                        NOT free 'p' and DOES NOT remove it from a scope
  35.  *                        list.  If it was a part of your intermediate code
  36.  *                        tree or another structure.  It will still be there.
  37.  *                          It is only removed from further consideration
  38.  *                        by the symbol table.
  39.  *    zzs_keydel(s)    --    Unlink the entry associated with key s.
  40.  *                        Calls zzs_del(p) to unlink.
  41.  *    zzs_scope(sc)    --    Specifies that everything added to the symbol
  42.  *                           table with zzs_add() is added to the list (scope)
  43.  *                        'sc'.  'sc' is of 'Sym **sc' type and must be
  44.  *                        initialized to NULL before trying to add anything
  45.  *                        to it (passing it to zzs_scope()).  Scopes can be
  46.  *                        switched at any time and merely links a set of
  47.  *                        symbol table entries.  If a NULL pointer is
  48.  *                        passed, the current scope is returned.
  49.  *    zzs_rmscope(sc)    --    Remove (zzs_del()) all elements of scope 'sc'
  50.  *                        from the symbol table.  The entries are NOT
  51.  *                        free()'d.  A pointer to the first
  52.  *                           element in the "scope" is returned.  The user
  53.  *                           can then manipulate the list as he/she chooses
  54.  *                           (such as freeing them all). NOTE that this
  55.  *                           function sets your scope pointer to NULL,
  56.  *                           but returns a pointer to the list for you to use.
  57.  *    zzs_stat()        --    Print out the symbol table and some relevant stats.
  58.  *    zzs_new(key)    --    Create a new record with calloc() of type Sym.
  59.  *                           Add 'key' to the string table and make the new
  60.  *                           records 'symbol' pointer point to it.
  61.  *    zzs_strdup(s)    --    Add s to the string table and return a pointer
  62.  *                           to it.  Very fast allocation routine
  63.  *                        and does not require strlen() nor calloc().
  64.  *
  65.  * Example:
  66.  *
  67.  *    #include <stdio.h>
  68.  *    #include "sym.h"
  69.  *
  70.  *    main()
  71.  *    {
  72.  *        Sym *scope1=NULL, *scope2=NULL, *a, *p;
  73.  *    
  74.  *        zzs_init(101, 100);
  75.  *    
  76.  *        a = zzs_new("Apple");    zzs_add(a->symbol, a);    -- No scope
  77.  *        zzs_scope( &scope1 );    -- enter scope 1
  78.  *        a = zzs_new("Plum");    zzs_add(a->symbol, a);
  79.  *        zzs_scope( &scope2 );    -- enter scope 2
  80.  *        a = zzs_new("Truck");    zzs_add(a->symbol, a);
  81.  *    
  82.  *        p = zzs_get("Plum");
  83.  *        if ( p == NULL ) fprintf(stderr, "Hmmm...Can't find 'Plum'\n");
  84.  *    
  85.  *        p = zzs_rmscope(&scope1)
  86.  *        for (; p!=NULL; p=p->scope) {printf("Scope1:  %s\n", p->symbol);}
  87.  *        p = zzs_rmscope(&scope2)
  88.  *        for (; p!=NULL; p=p->scope) {printf("Scope2:  %s\n", p->symbol);}
  89.  * }
  90.  *
  91.  * Terence Parr
  92.  * Purdue University
  93.  * February 1990
  94.  *
  95.  * CHANGES
  96.  *
  97.  *    Terence Parr
  98.  *    May 1991
  99.  *        Renamed functions to be consistent with ANTLR
  100.  *        Made HASH macro
  101.  *        Added zzs_keydel()
  102.  *        Added zzs_newadd()
  103.  *        Fixed up zzs_stat()
  104.  *
  105.  *    July 1991
  106.  *        Made symbol table entry save its hash code for fast comparison
  107.  *            during searching etc...
  108.  */
  109.  
  110. #include <stdio.h>
  111. #ifdef MEMCHK
  112. #include "trax.h"
  113. #else
  114. char *calloc();
  115. #endif
  116. #include "sym.h"
  117.  
  118. #define StrSame        0
  119.  
  120. static Sym **CurScope = NULL;
  121. static unsigned size = 0;
  122. static Sym **table=NULL;
  123. static char *strings;
  124. static char *strp;
  125. static int strsize = 0;
  126.  
  127. void
  128. zzs_init(sz, strs)
  129. int sz, strs;
  130. {
  131.     if ( sz <= 0 || strs <= 0 ) return;
  132.     table = (Sym **) calloc(sz, sizeof(Sym *));
  133.     if ( table == NULL )
  134.     {
  135.         fprintf(stderr, "Cannot allocate table of size %d\n", sz);
  136.         exit(1);
  137.     }
  138.     strings = (char *) calloc(strs, sizeof(char));
  139.     if ( strings == NULL )
  140.     {
  141.         fprintf(stderr, "Cannot allocate string table of size %d\n", strs);
  142.         exit(1);
  143.     }
  144.     size = sz;
  145.     strsize = strs;
  146.     strp = strings;
  147. }
  148.  
  149. void
  150. zzs_done()
  151. {
  152.     if ( table != NULL ) free( table );
  153.     if ( strings != NULL ) free( strings );
  154. }
  155.  
  156. void
  157. zzs_add(key, rec)
  158. char *key;
  159. register Sym *rec;
  160. {
  161.     register unsigned int h=0;
  162.     register char *p=key;
  163.     extern Sym *Globals;
  164.     
  165.     HASH(p, h);
  166.     rec->hash = h;                    /* save hash code for fast comp later */
  167.     h %= size;
  168.     
  169.     if ( CurScope != NULL ) {rec->scope = *CurScope; *CurScope = rec;}
  170.     rec->next = table[h];            /* Add to doubly-linked list */
  171.     rec->prev = NULL;
  172.     if ( rec->next != NULL ) (rec->next)->prev = rec;
  173.     table[h] = rec;
  174.     rec->head = &(table[h]);
  175. }
  176.  
  177. Sym *
  178. zzs_get(key)
  179. char *key;
  180. {
  181.     register unsigned int h=0;
  182.     register char *p=key;
  183.     register Sym *q;
  184.     
  185.     HASH(p, h);
  186.     
  187.     for (q = table[h%size]; q != NULL; q = q->next)
  188.     {
  189.         if ( q->hash == h )        /* do we even have a chance of matching? */
  190.             if ( strcmp(key, q->symbol) == StrSame ) return( q );
  191.     }
  192.     return( NULL );
  193. }
  194.  
  195. /*
  196.  * Unlink p from the symbol table.  Hopefully, it's actually in the
  197.  * symbol table.
  198.  *
  199.  * If p is not part of a bucket chain of the symbol table, bad things
  200.  * will happen.
  201.  *
  202.  * Will do nothing if all list pointers are NULL
  203.  */
  204. void
  205. zzs_del(p)
  206. register Sym *p;
  207. {
  208.     if ( p == NULL ) {fprintf(stderr, "zzs_del(NULL)\n"); exit(1);}
  209.     if ( p->prev == NULL )    /* Head of list */
  210.     {
  211.         register Sym **t = p->head;
  212.         
  213.         if ( t == NULL ) return;    /* not part of symbol table */
  214.         (*t) = p->next;
  215.         if ( (*t) != NULL ) (*t)->prev = NULL;
  216.     }
  217.     else
  218.     {
  219.         (p->prev)->next = p->next;
  220.         if ( p->next != NULL ) (p->next)->prev = p->prev;
  221.     }
  222.     p->next = p->prev = NULL;    /* not part of symbol table anymore */
  223.     p->head = NULL;
  224. }
  225.  
  226. void
  227. zzs_keydel(key)
  228. char *key;
  229. {
  230.     Sym *p = zzs_get(key);
  231.  
  232.     if ( p != NULL ) zzs_del( p );
  233. }
  234.  
  235. /* S c o p e  S t u f f */
  236.  
  237. /* Set current scope to 'scope'; return current scope if 'scope' == NULL */
  238. Sym **
  239. zzs_scope(scope)
  240. Sym **scope;
  241. {
  242.     if ( scope == NULL ) return( CurScope );
  243.     CurScope = scope;
  244.     return( scope );
  245. }
  246.  
  247. /* Remove a scope described by 'scope'.  Return pointer to 1st element in scope */
  248. Sym *
  249. zzs_rmscope(scope)
  250. register Sym **scope;
  251. {
  252.     register Sym *p;
  253.     Sym *start;
  254.  
  255.     if ( scope == NULL ) return(NULL);
  256.     start = p = *scope;
  257.     for (; p != NULL; p=p->scope) { zzs_del( p ); }
  258.     *scope = NULL;
  259.     return( start );
  260. }
  261.  
  262. void
  263. zzs_stat()
  264. {
  265.     static unsigned short count[20];
  266.     unsigned int i,n=0,low=0, hi=0;
  267.     register Sym **p;
  268.     float avg=0.0;
  269.     
  270.     for (i=0; i<20; i++) count[i] = 0;
  271.     for (p=table; p<&(table[size]); p++)
  272.     {
  273.         register Sym *q = *p;
  274.         unsigned int len;
  275.         
  276.         if ( q != NULL && low==0 ) low = p-table;
  277.         len = 0;
  278.         if ( q != NULL ) printf("[%d]", p-table);
  279.         while ( q != NULL )
  280.         {
  281.             len++;
  282.             n++;
  283.             printf(" %s", q->symbol);
  284.             q = q->next;
  285.             if ( q == NULL ) printf("\n");
  286.         }
  287.         if ( len>=20 ) printf("zzs_stat: count table too small\n");
  288.         else count[len]++;
  289.         if ( *p != NULL ) hi = p-table;
  290.     }
  291.  
  292.     printf("Storing %d recs used %d hash positions out of %d\n",
  293.             n, size-count[0], size);
  294.     printf("%f %% utilization\n",
  295.             ((float)(size-count[0]))/((float)size));
  296.     for (i=0; i<20; i++)
  297.     {
  298.         if ( count[i] != 0 )
  299.         {
  300.             avg += (((float)(i*count[i]))/((float)n)) * i;
  301.             printf("Buckets of len %d == %d (%f %% of recs)\n",
  302.                     i, count[i], 100.0*((float)(i*count[i]))/((float)n));
  303.         }
  304.     }
  305.     printf("Avg bucket length %f\n", avg);
  306.     printf("Range of hash function: %d..%d\n", low, hi);
  307. }
  308.  
  309. /*
  310.  * Given a string, this function allocates and returns a pointer to a
  311.  * symbol table record whose "symbol" pointer is reset to a position
  312.  * in the string table.
  313.  */
  314. Sym *
  315. zzs_new(text)
  316. char *text;
  317. {
  318.     Sym *p;
  319.     char *zzs_strdup();
  320.     
  321.     if ( (p = (Sym *) calloc(1,sizeof(Sym))) == 0 )
  322.     {
  323.         fprintf(stderr,"Out of memory\n");
  324.         exit(1);
  325.     }
  326.     p->symbol = zzs_strdup(text);
  327.     
  328.     return p;
  329. }
  330.  
  331. /* create a new symbol table entry and add it to the symbol table */
  332. Sym *
  333. zzs_newadd(text)
  334. char *text;
  335. {
  336.     Sym *p = zzs_new(text);
  337.     if ( p != NULL ) zzs_add(text, p);
  338.     return p;
  339. }
  340.  
  341. /* Add a string to the string table and return a pointer to it.
  342.  * Bump the pointer into the string table to next avail position.
  343.  */
  344. char *
  345. zzs_strdup(s)
  346. register char *s;
  347. {
  348.     register char *start=strp;
  349.  
  350.     while ( *s != '\0' )
  351.     {
  352.         if ( strp >= &(strings[strsize-2]) )
  353.         {
  354.             fprintf(stderr, "sym: string table overflow (%d chars)\n", strsize);
  355.             exit(-1);
  356.         }
  357.         *strp++ = *s++;
  358.     }
  359.     *strp++ = '\0';
  360.  
  361.     return( start );
  362. }
  363.